home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magnum One
/
Magnum One (Mid-American Digital) (Disc Manufacturing).iso
/
d12
/
cgazv5n4.arc
/
HZIP.C
< prev
next >
Wrap
C/C++ Source or Header
|
1991-09-23
|
11KB
|
395 lines
/*--- Listing 2 -------------------------- HZIP.C --------------
* Author: Anton Kruger, 5 October, 1990
*
* Copyright (c) Truda Software
*
* Source code may be freely used if authorship is acknowledged.
* Object code form may be used freely.
*
* Description: Routines that perform Huffman compression.
*
* Compilers: Turbo C++ 1.0, MSC 6.0
*
* Memory models: Any.
*
* Compile time switches:
* MAIN - if defined, a driver is provided
* DEBUG - if defined, the Huffman tree is displayed
*
* Compile notes: The encode() routine needs a little over 2K
* of stack space for its local variables. Turbo C's
* default stack size is adequate at 4K, but Microsoft
* only allocates 2K. To compile with Microsoft, you
* must increase the stack size with commands like:
*
* cl /W3 /DMAIN hzip.c
* link /STACK:0x1000 hzip.obj,hzip.exe;
*------------------------------------------------------------*/
#include <stdio.h>
#include "huff.h"
int huff_zip(char *infile,char *outfile);
void build_table(FILE *fp1);
void build_tree(void);
void write_head(FILE *fp);
void encode(FILE *fp1,FILE *fp2);
void build_codes(int (*codes)[2]);
void pack(int ib,int bits,FILE *fp);
void error(char *s);
#if defined(DEBUG)
void dump_tree(void);
#endif
#if defined(DEBUG) || defined(MAIN)
#include <stdlib.h>
#include <string.h>
#endif
#if defined(MAIN)
/* A small driver for the Huffman compression subroutine */
void main(int argc, char* argv[])
{
int i;
if (argc < 3)
error("Usage: HZIP infile outfile");
else{
i = huff_zip(argv[1],argv[2]);
switch (i){
case -1:
error("could not open input file...");
break;
case -2:
error("could not open output file...");
break;
default:
;
}
}
exit(0);
}
#endif
int huff_zip(char *infile,char *outfile)
{
/*
* This routine compresses "infile" with the Huffman
* algorithm. The output is written to the file "outfile".
*
* Return values:
* 0: normal return
* -1: could not open "infile"
* -2: could not open "outfile"
*/
FILE * fp1,*fp2;
/* Open I/O files with enlarged buffers for efficiency */
if ((fp1 = fopen(infile,"r+b")) != NULL)
setvbuf(fp1,NULL,_IOFBF,BUFFER_SIZE);
else
return(-1);
if ((fp2 = fopen(outfile,"w+b")) != NULL)
setvbuf(fp2,NULL,_IOFBF,BUFFER_SIZE);
else{
fclose(fp1);
return(-2);
}
/* Build symbol frequency table for "fname" */
build_table(fp1);
/* Build Huffman tree using frequency tables */
build_tree();
write_head(fp2); /* Write file header to output file */
encode(fp1,fp2); /* Encode using Huffman tree */
fclose(fp1); /* Clean up, and return to caller */
fclose(fp2);
return(0);
}
void build_table(FILE* fp1)
{
/*
* This routine makes the symbol frequency tables needed
* to build the Huffman tree. It also determines number of
* characters in the input file, "nchars", as well as
* number of unique symbols, "nsymbols".
*/
int i,j;
int indx;
for (i=0;i<=MAXSYM-1;i++) /* Clear the frequency table */
freq[i] = 0;
/* Count # of times a character occur in the input file */
indx = getc(fp1);
while (!feof(fp1)){
freq[indx]++;
indx = getc(fp1);
}
rewind(fp1);
/* Determine # of chars in input file */
for (nchars=0,i=0;i<=MAXSYM-1;i++)
nchars = nchars + freq[i];
/* Initialize the "symbol"s table */
for (i=0;i<=MAXSYM-1;i++)
symbol[i] = (unsigned char)i;
/*
* Pack the tables so that they are contiguous in memory.
* That is, the tables occupy the first block of elements
* in their respective arrays.
*/
for(i=0,j=0;j<=MAXSYM-1;j++){
if (freq[j] != 0) { /* => symbol occurs in input file */
freq[i] = freq[j];
symbol[i] = symbol[j];
if (i!=j) freq[j] = 0;
i++;
}
}
nsymbols = i;
}
void build_tree(void)
{
/* This routine builds the Huffman tree */
int root; /* Location of the root of the tree */
int j,m;
int n1,n2;
unsigned long small1,small2;
/* Initialize the Huffman tree */
root = (2*nsymbols-1) - 1;
for (j=0;j<=root;j++)
father[j] = left_son[j] = right_son[j] = NONE;
/* Build Huffman tree */
for (m=nsymbols;m<=root;m++){
small1 = small2 = ULONG_MAX;
/* Search for smallest node with no father */
for (j=0; j<=m-1; j++){
if (father[j] == NONE){
if (freq[j] < small1 && freq[j] != 0){
small1 = freq[j];
n1 = j;
}
}
}
/* Search for the second most smallest node
with no father */
for (j=0; j<=m-1; j++){
if (father[j] == NONE){
if (freq[j] < small2 &&
freq[j] >= small1 && j != n1){
small2 = freq[j];
n2 = j;
}
}
}
/* Build a new node */
left_son[m] = n1; /* Found a (left) son at node n1 */
right_son[m] = n2; /* Found a (right) son at node n2 */
father[n1] = m; /* node n1's father is node m */
father[n2] = m; /* node n2's father is node m */
freq[m] = freq[n1]+freq[n2]; /* father has combined
frequency of sons */
}
#if defined(DEBUG)
dump_tree();
#endif
}
void write_head (FILE * fp)
{
/*
* This routine writes the file header to the output file.
* The header starts off with three identification bytes
* that the decompression routine must check before
* attempting decoding. Following this are the components
* of the Huffman tree that are needed for decoding.
*/
int root;
/* Write the characters "CH1" */
putc('C',fp); /* ID Byte */
putc('H',fp); /* => Huffman encoding */
putc('1',fp); /* Version 1 */
root = (2*nsymbols-1) - 1;
fwrite(&nchars,sizeof(nchars),1,fp);
fwrite(&root,sizeof(root),1,fp);
fwrite(left_son,sizeof(left_son[1]),root+1,fp);
fwrite(right_son,sizeof(right_son[1]),root+1,fp);
fwrite(&nsymbols,sizeof(nsymbols),1,fp);
fwrite(symbol,sizeof(symbol[1]),nsymbols,fp);
}
void encode(FILE *fp1, FILE *fp2)
{
/*
* This routine encodes the input file. First, the routine
* "build_codes" is called to set up a table that holds the
* Huffman code for each symbol in the input file. For each
* character in the input file the corresponding code is
* looked up, and packed away in the output file.
*/
int codes[MAXNOD][2];
int i,ib,bits;
unsigned long k;
/* Generate Huffman "code"s table for file */
build_codes(codes);
for (k=1;k<=nchars;k++){
/* Get a character from the input file */
i = (int)getc(fp1);
/* Look up character's Huffman code */
bits = codes[i][0];
/* Look up the number of bits in code */
ib = codes[i][1];
/* Pack character's code away in output file */
pack(ib,bits,fp2);
}
/*
* The stream of bits may not make up an integral number
* of bytes, so some bits may remain unwritten. Flush all
* bits by writing 16 zero bits; this will also make the
* last byte in the output file 0.
*/
bits = 0;
pack(15,bits,fp2);
}
void build_codes(int codes[][2])
{
/*
* This routine fills the table "codes" with the Huffman
* codes for the input file. It starts at a symbol's
* terminal node, and moves up the tree until the root is
* reached (i.e., father == NONE), collecting "1" bits if
* the current node is a left son, or "0" bits otherwise.
* This procedure is repeated for all symbols.
*/
int ib,bits;
int j,node;
unsigned char k;
for (j=0;j<=nsymbols-1;j++){
bits = ib = 0;
node = j;
while (father[node] != NONE){
if (node==left_son[father[node]])
/* set bit if node is a left son */
bits = (int)ibset(bits,ib);
else /* leave bit cleared if right son */
;
ib++;
/* move up one node closer to root */
node = father[node];
}
ib--;
k = symbol[j];
codes[k][0] = bits; /* Store code for symbol[j] */
codes[k][1] = ib; /* Store # of bits in code
for symbol[j] */
}
}
void pack(int ib,int bits,FILE* fp)
{
/*
* This routine starts at bit-position "ib" in "bits"
* and scans for set bits. For every set bit found,
* a corresponding bit is set in "byte".
* When "byte" is full, it is written to the output file.
*/
static char ip = 7; /* Keeps track of next
open bit in "byte" */
static char byte = 0;
while (ib >= 0){
byte = btest(bits,ib) ? (char)ibset(byte,ip) : byte;
if (--ip < 0){
putc(byte,fp);
byte = 0;
ip = 7;
}
ib--;
}
}
void error(char *s)
{
fprintf(stderr,"Error: %s\n",s);
exit(-1);
}
#ifdef DEBUG
/* debugging routine - displays contents of tree */
void dump_tree(void)
{
int root,i;
int c;
char str[10];
root = (2*nsymbols-1) - 1;
printf("******************************"
"******************************\n");
printf(" i symbol freq(i) father(i)"
" left_son(i) right_son(i)\n");
printf("******************************"
"******************************\n");
for (i=0; i<=root; i++){
if (i == nsymbols)
printf("----------------------------"
"--------------------------------\n");
c = symbol[i];
str[0] = (char) c;
str[1] = '\0';
if ((int)c == 0) strcpy(str,"NULL");
if ((int)c == 7) strcpy(str,"BELL");
if ((int)c == 8) strcpy(str,"BS");
if ((int)c == 9) strcpy(str,"TAB");
if ((int)c == 10) strcpy(str,"LF");
if ((int)c == 11) strcpy(str,"VT");
if ((int)c == 12) strcpy(str,"FF");
if ((int)c == 13) strcpy(str,"CR");
if ((int)c == 26) strcpy(str,"EOF");
if ((int)c == 32) strcpy(str,"SPACE");
if (i >= nsymbols)
str[0] = '\0';
printf("%4d %5s %7d %8d %11d %13d\n",i,
str,
(int)freq[i],
(int)father[i],
(int)left_son[i],
(int)right_son[i]);
}
}
#endif